class Solution {
public:
    vector<string> ret;
    unordered_map<char, string> hash = { {'2', "abc"}, {'3', "def"}, {'4', "ghi"}
    , {'5', "jkl"}, {'6', "mno"}, {'7', "pqrs"}, {'8', "tuv"}, {'9', "wxyz"} };
    void dfs(string& digits, int n, string out)
    {
        if(n == digits.size())
        {
            ret.push_back(out);
            return;
        }
        for(int i = 0; i < hash[digits[n]].size(); i++)
        {
            dfs(digits, n + 1, out + hash[digits[n]][i]);
        }
    }
    vector<string> letterCombinations(string digits) {
        if(digits == "") return ret;
        dfs(digits, 0, "");
        return ret;
    }
};